class Solution {
public:
    vector<int> countBits(int n)
    {
        vector<int> ret(n + 1);
        ret[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            int sum = 0, tmp = i;
            while (tmp > 0)
            {
                tmp = tmp & (tmp - 1);
                sum++;
            }
            ret[i] = sum;
        }
        return ret;

    }
};